`
https://leetcode.cn/problems/delete-operation-for-two-strings/
`

/**
 * @param {string} word1
 * @param {string} word2
 * @return {number}
 */
var minDistance = function (word1, word2) {
  const m = word1.length, n = word2.length

  // 存储已经计算的结果
  const memo = Array.from({ length: m }, () => new Array(n).fill(-1))

  // dp(i, j) 表示使得 word1[0...i] 和 word2[0...j] 相同所需的最少删除次数
  function dp(i, j) {
    // 如果有一个字符串遍历完了，就把另一个没遍历完的剩下部分全删掉即可
    if (i === m) {
      return n - j
    }
    if (j === n) {
      return m - i
    }

    // 如果已经计算过了，直接返回缓存里的值即可
    if (memo[i][j] !== -1) {
      return memo[i][j]
    }

    if (word1[i] === word2[j]) {
      memo[i][j] = dp(i + 1, j + 1)
    } else {
      memo[i][j] = Math.min(
        // 删掉 word1[i]
        dp(i + 1, j) + 1,
        // 删掉 word2[j]
        dp(i, j + 1) + 1
      )
    }

    return memo[i][j]
  }

  return dp(0, 0)
};